package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC_655_PrintBinaryTree {

    public static void main(String[] args) {

    }

    class Solution {
        public List<List<String>> printTree(TreeNode root) {
            int height = getHeight(root);
            int size = (int) Math.pow(2, height) - 1;
            List<List<String>> result = new ArrayList<>();
            for (int i = 0; i < height; i++) {
                List<String> list = new ArrayList<>();
                for (int j = 0; j < size; j++) {
                    list.add("");
                }
                result.add(list);
            }
            helper(result, root, 0, 0, size - 1);
            return result;
        }

        void helper(List<List<String>> result, TreeNode node, int level, int left, int right) {
            if (node == null) {
                return;
            }
            int index = (left + right) / 2;
            result.get(level).set(index, node.val + "");
            helper(result, node.left, level + 1, left, index - 1);
            helper(result, node.right, level + 1, index + 1, right);
        }

        int getHeight(TreeNode node) {
            if (node == null) {
                return 0;
            }
            return Math.max(1 + getHeight(node.left), 1 + getHeight(node.right));
        }
    }

    public class Solution_2 {
        public List<List<String>> printTree(TreeNode root) {
            int height = getHeight(root);
            String[][] res = new String[height][(1 << height) - 1];
            for (String[] arr : res)
                Arrays.fill(arr, "");
            List<List<String>> ans = new ArrayList<>();
            fill(res, root, 0, 0, res[0].length);
            for (String[] arr : res)
                ans.add(Arrays.asList(arr));
            return ans;
        }

        void fill(String[][] res, TreeNode root, int i, int l, int r) {
            if (root == null)
                return;
            res[i][(l + r) / 2] = "" + root.val;
            fill(res, root.left, i + 1, l, (l + r) / 2);
            fill(res, root.right, i + 1, (l + r + 1) / 2, r);
        }

        int getHeight(TreeNode root) {
            if (root == null)
                return 0;
            return 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }
    }

}